package Intermediate_algorithm.ArrayAndString;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

/*
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的最长 子串的长度。

示例1:
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
    请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。

提示：
0 <= s.length <= 5 * 104
s由英文字母、数字、符号和空格组成
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xv2kgi/
 */
public class _04无重复字符的最长子串 {

    @Test
    public void test() {
        System.out.println(lengthOfLongestSubstring2("abcabcbb"));
    }

    //DP
    //先获得每个index前的无重复字符的最长子串数组
    //遍历该数组的最大值
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n < 2) return n;
        ArrayList<Character> set = new ArrayList<>();
        int res = 0;
        int[] count = new int[n];
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (!set.contains(c)) {
                set.add(c);
                count[i] = set.size();
            }else {
                int indexOf = set.indexOf(c);
                while (indexOf != -1) {
                    set.remove(indexOf);
                    indexOf--;
                }
                set.add(c);
                count[i] = set.size();
            }
        }
        for (int i = 0; i < n; i++) {
            res = Math.max(res, count[i]);
        }
        return res;
    }

    //官解：方法一：滑动窗口
    //答题执行用时和DP差不多
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/227999/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
     */
    //ps: 子串问题可以思考滑动窗口方法
    class Solution {
        public int lengthOfLongestSubstring(String s) {
            // 哈希集合，记录每个字符是否出现过
            Set<Character> occ = new HashSet<Character>();
            int n = s.length();
            // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
            int rk = -1, ans = 0;
            for (int i = 0; i < n; ++i) {
                if (i != 0) {
                    // 左指针向右移动一格，移除一个字符
                    occ.remove(s.charAt(i - 1));
                }
                while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                    // 不断地移动右指针
                    occ.add(s.charAt(rk + 1));
                    ++rk;
                }
                // 第 i 到 rk 个字符是一个极长的无重复字符子串
                ans = Math.max(ans, rk - i + 1);
            }
            return ans;
        }
    }

    //滑动窗口
    public int lengthOfLongestSubstring2(String s) {
        int n = s.length();
        if (n < 2) return n;
//        ArrayList<Character> set = new ArrayList<>();
        //hashSet比ArrayList速度快  猜测：remove时候查询方式不同导致效率问题
        HashSet<Character> set = new HashSet<>();
        int p = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (p == n - 1){
                break;
            }
            if (i != 0){
                set.remove((Character) s.charAt(i - 1));
            }
            while (p < n && !set.contains(s.charAt(p))) {
                set.add(s.charAt(p));
                p++;
            }
            res = Math.max(res, p - i);
        }
        return res;
    }

}
